package Sort;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-05-17 10:42
 *
 * 归并排序的应用：
 * 315. 计算右侧小于当前元素的个数
 */
public class MergeSort {

    /** ===========================================================================================================================
     * 315. 计算右侧小于当前元素的个数
     *  给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
     * 思路：利用merge的过程，在合并两个有序数组的时候是可以知道i后面有多少元素比i小的。
     * */
    //需要用一个数据结构能跟随排序的过程记录元素原本的下标位置，用于计算结果
    private class ValToIndex{
        int val,index;
        ValToIndex(int val,int index){
            this.val=val;
            this.index=index;
        }
    }
    //merge的辅助数组
    ValToIndex[] temp;
    int[] count;

    private void MergeSort(ValToIndex[] arr,int l,int r){
        if(r<=l) return;
        int mid=l+(r-l)/2;
        MergeSort(arr,l,mid);
        MergeSort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
    private void  merge(ValToIndex[] arr,int l,int mid,int r){
        for (int k = l; k <= r; k++) {
            temp[k]=arr[k];
        }
        int i=l,j=mid+1;
        for (int k = l; k <= r; k++) {
            if(i>=mid+1){
                arr[k]=temp[j++];
            }else if (j>r){
                arr[k]=temp[i++];
                //此时后半段都合并完成了，则前半段剩余的元素全部都是大于后半段的
                count[arr[k].index]+=(j-mid-1);
            }else if (temp[i].val<=temp[j].val){
                //[mid+1,j)范围内是在i后面比i小的元素
                arr[k]=temp[i++];
                count[arr[k].index]+=(j-mid-1);
            }else {
                arr[k]=temp[j++];
            }
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        int n=nums.length;
        temp=new ValToIndex[n];
        count=new int[n];
        ValToIndex[] arr=new ValToIndex[n];
        for (int i = 0; i < n; i++) {
            arr[i]=new ValToIndex(nums[i], i);
        }
        MergeSort(arr,0,n-1);
        List<Integer> res=new LinkedList<>();
        for (int c:count) {
            res.add(c);
        }
        return res;
    }

    /** ===========================================================================================================================
     * 493. 翻转对
     *  给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
     *  思路：这道题和上道题的区别只在于要找到count数组为i之后且大于i的两倍的元素个数，然后再将count数组求和就是答案。merge 函数中做点手脚，当 nums[lo..mid] 和 nums[mid+1..hi] 两个子数组完成排序后，对于 nums[lo..mid] 中的每个元素 nums[i]，去 nums[mid+1..hi] 中寻找符合条件的 nums[j] 就行了。
     *   在寻找符合条件的nums[j]时不需要去遍历nums[mid+1..hi]，只要维护一个开区间边界 end，维护 nums[mid+1..end-1] 是符合条件的元素即可。因为nums[mid+1..hi]是有序的
     * */
    int[] temp1;
    int count1=0;
    void mergeSort(int[] nums,int l,int r){
        if(r<=l) return;
        int mid=l+(r-l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }
    void merge(int[] nums,int l,int mid,int r){
        for (int k = l; k <= r; k++) {
            temp1[k]=nums[k];
        }
        // 进行效率优化，维护左闭右开区间 [mid+1, end) 中的元素乘 2 小于 nums[i]
        // 为什么 end 是开区间？因为这样的话可以保证初始区间 [mid+1, mid+1) 是一个空区间
        int end=mid+1;
        for (int k = l; k <= mid; k++) {
            while (end<=r&&(long)nums[k]>(long) nums[end]*2){
                end++;
            }
            count1+=(end-mid-1);
        }
        int i=l,j=mid+1;
        for (int k = l; k <=r ; k++) {
            if(i>=mid+1){
                nums[k]=temp1[j++];
            }else if(j>=r+1){
                nums[k]=temp1[i++];
            }else if(temp1[i]<=temp1[j]){
                nums[k]=temp1[i++];
            }else {
                nums[k]=temp1[j++];
            }
        }
    }

    public int reversePairs(int[] nums) {
        temp1=new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return count1;
    }

    /** ===========================================================================================================================
     * 327. 区间和的个数
     *  给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
     *  区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
     *
     *  思路：需要快速求区间和，所以构造前缀和，这样题目就变成了在前缀和数组中求数组count，使得count的中元素表示，
     *  从i之后的且值减去i在[lower, upper] 范围内的元素个数，然后将这个count数组求和得到结果
     * */
    int lower,upper,count2=0;
    long[] temp2;
    void mergeSort(long[] nums,int l,int r){
        if (r<=l) return;
        int mid=l+(r-l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums, l, mid, r);
    }
    void merge(long[] nums,int l,int mid,int r){
        for (int k = l; k <= r; k++) {
            temp2[k]=nums[k];
        }
        // 进行效率优化
        // 维护左闭右开区间 [start, end) 中的元素和 nums[i] 的差在 [lower, upper] 中
        int start=mid+1,end=mid+1;
        for (int k = l; k <= mid; k++) {
            // 如果 nums[i] 对应的区间是 [start, end)，
            // 那么 nums[i+1] 对应的区间一定会整体右移，类似滑动窗口
            while (start<=r&&nums[start]-nums[k]<lower){
                start++;
            }
            while (end<=r&&nums[end]-nums[k]<=upper){
                end++;
            }
            count2+=(end-start);
        }
        int i=l,j=mid+1;
        for (int k = l; k <= r; k++) {
            if(i==mid+1){
                nums[k]=temp2[j++];
            }else if(j==r+1){
                nums[k]=temp2[i++];
            }else if (temp2[i]<=temp2[j]){
                nums[k]=temp2[i++];
            }else {
                nums[k]=temp2[j++];
            }
        }
    }
    public int countRangeSum(int[] nums, int lower, int upper) {
        this.lower=lower;
        this.upper=upper;
        temp2=new long[nums.length+1];
        long[] preSum=new long[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i+1]=(long) nums[i]+preSum[i];
        }
        mergeSort(preSum,0,preSum.length-1);
        return count2;
    }

}
